package hot100;

public class canPartition2 {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for(int x : nums) {
            total += x;
        }
        //和为奇数
        if(total % 2 != 0) {
            return false;
        }
        //背包容量，目标价值
        int target = total / 2;
        int n = nums.length;

        boolean[][] dp = new boolean[n+1][target + 1];

        for(int i = 0;i <= n;i++) {
            dp[i][0] = true;
        }

        for(int i = 1;i < n;i++) {
            for(int j = 1;j <= target;j++) {
                if(j < nums[i]) {
                    dp[i][j] = dp[i - 1][j];
                }else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[n - 1][target];
    }
}
